package J20241102_dichotomy;

/**
 * Created with IntelliJ IDEA.
 * Description: 整数二分
 * User: 王圆豪
 * Date: 2024-11-04
 * Time: 21:02
 */
public class Test_Dichotomy_Int {
    public static void main(String[] args) {
        int[] arr = new int[]{1,2,2,3,3,3,5};
        int target = 5;
        int l = leftBoundary(arr, target);
        int r = rightBoundary(arr, target);
        System.out.println(l + " " + r);
    }

    private static int rightBoundary(int[] arr, int target) {
        int l = 0,r = arr.length - 1;
        while(l < r){
            int mid = (l + r + 1) / 2;
            if (arr[mid] <= target){
                l = mid;
            }else {
                r = mid - 1;
            }
        }
        return l;
    }

    private static int leftBoundary(int[] arr, int target) {
        int l = 0,r = arr.length - 1;
        while(l < r){
            int mid = (l + r) / 2;
            if (arr[mid] >= target){
                r = mid;
            }else {
                l = mid + 1;
            }
        }
        return l;
    }
}
